#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<unordered_set>
#include<unordered_map>
using namespace std;

class Solution{
    public:
    int ans1(string startGene, string endGene, vector<string>& bank){
        unordered_set<string> cnt;
        unordered_set<string> visited;
        char keys[4] = {'A', 'C', 'G', 'T'};        
        for (auto & w : bank) {
            cnt.emplace(w);
        }
        if (startGene == endGene) {
            return 0;
        }
        if (!cnt.count(endGene)) {
            return -1;
        }
        queue<string> qu;
        qu.emplace(startGene);
        visited.emplace(startGene);
        int step = 1;
        while (!qu.empty()) {
            int sz = qu.size();
            for (int i = 0; i < sz; i++) {
                string curr = qu.front();
                qu.pop();
                for (int j = 0; j < 8; j++) {
                    for (int k = 0; k < 4; k++) {
                        if (keys[k] != curr[j]) {
                            string next = curr;
                            next[j] = keys[k];
                            if (!visited.count(next) && cnt.count(next)) {
                                if (next == endGene) {
                                    return step;
                                }
                                qu.emplace(next);
                                visited.emplace(next);
                            }
                        }
                    }
                }
            }
            step++;
        }
        return -1;
    }

    // int ans2(string startGene, string endGene, vector<string>& bank){
    //     int len = bank.size();
    //     int ans = 0;
    //     vector<pair<int, string>> map;
    //     vector<int> val_bank(len, 0);
    //     for(int i = 0; i != len; i++){
    //         map.push_back(pair(compare(startGene, bank[i]), bank[i]));
    //     }
    //     if(startGene == endGene){
    //         return 0;
    //     }
    //     if(!map.count(endGene)){
    //         return -1;
    //     }
    //     sort(map.begin(), map.end());
    //     return ans;
    // }
    // int compare(string startGene, string endGene){
    //     int ans = 0;
    //     for(int i = 0; i != 8; i++){
    //         if(startGene[i] != endGene[i]){
    //             ans++;
    //         }
    //     }
    //     return ans;
    // }
    
    int compare(string& str1, string& str2){
        int ret = 0;
        for(int i = 0; i != m_len; i++){
            if(str1[i] != str2[i]){
                ret++;
            }
        }
        return ret;
    }

    int ans3(string startGene, string endGene, vector<string>& bank){
        int n = bank.size();
        int ret = 0;
        queue<string> strQ;
        strQ.push(startGene);
        int len = 1;
        while(!strQ.empty()){
            while(len > 0){
                string temp = strQ.front();
                strQ.pop();
                bankpassed.insert(temp);
                len--;
                if(temp == endGene){
                    return ret;
                }
                for(int i = 0; i != n; i++){
                    if(compare(temp, bank[i]) == 1 && bank[i] != startGene){
                        if(bankpassed.find(bank[i]) == bankpassed.end()){
                            strQ.push(bank[i]);
                            bankpassed.insert(bank[i]);
                        }
                    }
                }
            }
            len = strQ.size();
            ret++;
        }
        return -1;
    }

    private:
    int m_len = 8;
    unordered_set<string> bankpassed;
};

void test1(){
    Solution s;
    string start = "AACCGGTT", end = "AACCGGTA";
    vector<string> bank = {
        "AACCGGTA"
    };

    // int ret = s.ans1(start, end, bank);
    // int ret = s.ans2(start, end, bank);
    int ret = s.ans3(start, end, bank);
    cout << ret << endl;
}

void test2(){
    Solution s;
    string start = "AACCGGTT", end = "AAACGGTA";
    vector<string> bank = {
        "AACCGGTA","AACCGCTA","AAACGGTA"
    };

    // int ret = s.ans1(start, end, bank);
    // int ret = s.ans2(start, end, bank);
    int ret = s.ans3(start, end, bank);
    cout << ret << endl;
}

void test3(){
    Solution s;
    string start = "AAAAACCC", end = "AACCCCCC";
    vector<string> bank = {
        "AAAACCCC","AAACCCCC","AACCCCCC"
    };

    // int ret = s.ans1(start, end, bank);
    // int ret = s.ans2(start, end, bank);
    int ret = s.ans3(start, end, bank);
    cout << ret << endl;
}

int main(void){
    test1();
    test2();
    test3();

    return 0;
}